﻿using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Threading.Tasks;

namespace ImageK.Util
{
    /** A simple QuickSort for String arrays. */
    public class StringSorter
    {
        /** Sorts the array. */
        public static void sort(string[] a)
        {
            if (a==null)
                return;
            if (!alreadySorted(a))
                sort(a, 0, a.Length - 1);
        }

        static void sort(String[] a, int from, int to)
        {
            int i = from, j = to;
            string center = a[(from + to) / 2];
            do
            {
                while (i < to && string.Compare(center, a[i], StringComparison.Ordinal) > 0) i++;
                while (j > from && string.Compare(center, a[j], StringComparison.Ordinal) < 0) j--;
                if (i < j) { string temp = a[i]; a[i] = a[j]; a[j] = temp; }
                if (i <= j) { i++; j--; }
            } while (i <= j);
            if (from < j) sort(a, from, j);
            if (i < to) sort(a, i, to);
        }

        static bool alreadySorted(string[] a)
        {
            for (int i = 1; i<a.Length; i++)
            {
                if (string.Compare(a[i], a[i-1], StringComparison.Ordinal) < 0)
                    return false;
            }
            return true;
        }

        /** Sorts file names containing numerical components.
        * Author: Norbert Vischer
        */
        public static string[] sortNumerically(string[] list)
        {
            int n = list.Length;
            string[] paddedList = getPaddedNames(list);
            string[] sortedList = new string[n];
            int[] indexes = Tools.rank(paddedList);
            for (int i = 0; i < n; i++)
                sortedList[i] = list[indexes[i]];
            return sortedList;
        }

        // Pads individual numeric string components with zeroes for correct sorting
        private static String[] getPaddedNames(String[] names)
        {
            int nNames = names.Length;
            String[] paddedNames = new String[nNames];
            int maxLen = 0;
            for (int jj = 0; jj < nNames; jj++)
            {
                if (names[jj].Length > maxLen)
                {
                    maxLen = names[jj].Length;
                }
            }
            int maxNums = maxLen / 2 + 1;//calc array sizes
            int[,] numberStarts = new int[names.Length, maxNums];
            int[,] numberLengths = new int[names.Length,maxNums];
            int[] maxDigits = new int[maxNums];

            //a) record position and digit count of 1st, 2nd, .. n-th number in string
            for (int jj = 0; jj < names.Length; jj++)
            {
                String name = names[jj];
                bool inNumber = false;
                int nNumbers = 0;
                int nDigits = 0;
                for (int pos = 0; pos < name.Length; pos++)
                {
                    bool isDigit = name[pos] >= '0' && name[pos] <= '9';
                    if (isDigit)
                    {
                        nDigits++;
                        if (!inNumber)
                        {
                            numberStarts[jj,nNumbers] = pos;
                            inNumber = true;
                        }
                    }
                    if (inNumber && (!isDigit || (pos == name.Length - 1)))
                    {
                        inNumber = false;
                        if (maxDigits[nNumbers] < nDigits)
                        {
                            maxDigits[nNumbers] = nDigits;
                        }
                        numberLengths[jj,nNumbers] = nDigits;
                        nNumbers++;
                        nDigits = 0;
                    }
                }
            }

            //b) perform padding
            for (int jj = 0; jj < names.Length; jj++)
            {
                String name = names[jj];
                int numIndex = 0;
                StringBuilder destName = new StringBuilder();
                for (int srcPtr = 0; srcPtr < name.Length; srcPtr++)
                {
                    if (srcPtr == numberStarts[jj,numIndex])
                    {
                        int numLen = numberLengths[jj,numIndex];
                        if (numLen > 0)
                        {
                            for (int pad = 0; pad < (maxDigits[numIndex] - numLen); pad++)
                            {
                                destName.Append('0');
                            }
                        }
                        numIndex++;
                    }
                    destName.Append(name[srcPtr]);
                }
                paddedNames[jj] = destName.ToString();
            }
            return paddedNames;
        }
    }
}
